1143 最长公共子序列

给定两个字符串  text1  和  text2 ，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回  0  。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如， "ace"  是  "abcde"  的子序列，但  "aec"  不是  "abcde"  的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

** 输入：**text1 = "abcde", text2 = "ace" ** 输出：**3
** 解释：** 最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

** 输入：**text1 = "abc", text2 = "abc" ** 输出：**3 ** 解释：** 最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

** 输入：**text1 = "abc", text2 = "def" ** 输出：**0 ** 解释：** 两个字符串没有公共子序列，返回 0 。

考虑 s [i] 和 t [j] 的选与不选 如果他俩相等 那么步进 dfs (i-1,j-1)+1 如果他俩不等 那么会不选某一边 max (dfs (i-1,j)+dfs (i,j-1)) 相等的时候需要不选某一个吗？不行 不等的时候可以都不选或都选吗？不行

function longestCommonSubsequence(s, t) {
    const n = s.length, m = t.length;
    const memo = new Map();

    function dfs(i, j) {
        if (i < 0 || j < 0) return 0;
        const key = `${i},${j}`;
        if (memo.has(key)) return memo.get(key);
        let res;
        if (s[i] === t[j]) {
            res = dfs(i - 1, j - 1) + 1;
        } else {
            res = Math.max(dfs(i - 1, j), dfs(i, j - 1));
        }
        memo.set(key, res);
        return res;
    }

    return dfs(n - 1, m - 1);
}